/**
 * 邻接表存储图
 * 用深度优先和广度优先判断是否存在vi到vj的路径
 * 
 * 两个算法的思想一样：都是从i开始查找，如果能找打就返回true，否则返回false
 */

#include"store_table.h"

#define bfs
int visited[MAX_VERTEX_NUM]={0};

#ifdef dfs
void dfs(ALGraph *g,int i,int j,bool &can_reach){
    if(i==j){
        can_reach=true;
        return;//如果i=j就是遍历到了
    }
    visited[i]=1;
    //从i的下一个节点开始，能找到下一个节点就递归进去
    for (int p = firstNeighbor(g,i); p >=0; p=nextNeighbor(g,i,p))
    {
        if(!visited[p]&&!can_reach)
            dfs(g,p,j,can_reach);
    }
}
#endif

#ifdef bfs
#include<queue>
using namespace std;
void bfs(ALGraph *g,int i,int j){
    queue<int> q;
    while (!q.empty())
    {
        i=q.front();q.pop();
        visited[i]=1;
        if(i==j) return 1;
        for(int p=firstNeighbor(g,i);p;p=nextNeighbor(g,i,p)){
            if(p==j)return 1;
            if(!visited[p]){
                q.push_back(p);
                visited[p]=1;
            }
        }
    }
    return 0;

}

#endif